package com.example.arithmeticleetcode.leetcode.dec;

import java.util.*;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2020-12-30 09:22
 **/
public class Demo28 {

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4, 5};
        int[] arr2 = {1, 1, 3, 5, 5};
        int[] arr3 = {6, 7, 11, 7, 6, 8};
        getStrongest(arr1, 2);
        getStrongest(arr2, 2);
        getStrongest(arr3, 5);
        getStrongest2(arr1, 2);
        getStrongest2(arr2, 2);
        getStrongest2(arr3, 5);
    }

    public static int[] getStrongest2(int[] arr, int k) {
        Arrays.sort(arr);
        int mid = arr[(arr.length - 1) >> 1];
        int[] retArr = new int[k];
        int begin = 0, end = arr.length - 1, curIndex = 0;
        while (k > curIndex) {
            if (arr[end] - mid >= mid - arr[begin]) {
                retArr[curIndex++] = arr[end];
                end--;
            } else {
                retArr[curIndex++] = arr[begin];
                begin++;
            }
        }
        return retArr;
    }


    public static int[] getStrongest(int[] arr, int k) {
        int[] sortArr = new int[arr.length];
        System.arraycopy(arr, 0, sortArr, 0, arr.length);
        Arrays.sort(sortArr);
        int mid = sortArr[(arr.length - 1) >> 1];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            int diff = Math.abs(arr[i] - mid);
            List<Integer> list = map.containsKey(diff) ? map.get(diff) : new ArrayList<>();
            list.add(arr[i]);
            map.put(diff, list);
        }
        ArrayList<Integer> integers = new ArrayList<>(map.keySet());
        Collections.sort(integers, (o1, o2) -> o2 - o1);
        int[] ints = new int[k];
        int count = 0;
        for (Integer integer : integers) {
            List<Integer> list = map.get(integer);
            Collections.sort(list, (o1, o2) -> o2 - o1);
            for (Integer integer1 : list) {
                if (k == count) break;
                ints[count++] = integer1;
            }
            if (k == count) break;
        }
        return ints;
    }
}
